#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdlib>

#include <sys/types.h>
#include <sys/stat.h>
#include <errno.h>

#include <sys/time.h>
using namespace std;

#define swap(a, b) \
	if(a != b) \
	{ a ^= b;	b ^= a; a ^= b; }
#define swap2(t, a, b) \
	{ t _ = a; a = b; b = _; }

typedef int int4;
/**
 * function declaration
 */
inline int fw_search2(const int tag, int4 *arr, int len);
inline int bw_search(const int tag, int* arr, int len);
int intersection(int* a1, int l1, int* a2, int l2);
void show_list(int* arr, int len);
void init_list(int* arr, int len);
inline int binary_search(int4 tag, int4* arr, int l, int h);
int merge(int* a1, int l1, int* a2, int l2);




int main(int argc, char* argv[])
{
	srand(time(0));
	
	int l1 = 50 + rand() % 100;
	int l2 = l1 + rand() % 100;
	
	int4* a1 = new int4[l1];
	int4* a3 = new int4[l1];
	int4* a2 = new int4[l2];
	
	
	init_list(a1, l1);
	init_list(a2, l2);
	
	/*
	int l1 = 5;
	int l2 = 9;
	
	int4 a1[] = {5, 8, 12, 16, 18};
	int4 a3[] = {5, 8, 12, 16, 18};
	int4 a2[] = {4, 8, 11, 16, 17, 21, 22, 25, 26};
	*/
	
	for(int i = 0; i < l1; i++)
	{
		a3[i] = a1[i];
	}
	
	show_list(a1, l1);
	show_list(a2, l2);
	cout<<endl<<endl;
	int n = merge(a1, l1, a2, l2);
	
	cout<<"------"<<endl;
	show_list(a1, n);
	n = intersection(a3, l1, a2, l2);
	
	cout<<"------"<<endl;
	show_list(a1, n);
	
	return 0;
}


int merge(int* a1, int l1, int* a2, int l2)
{
	int i = 0;
	int j = 0;
	int n = 0;
	
	for(; i < l1 && j < l2;)
	{
		if(a1[i] == a2[j])
		{
			a1[n++] = a1[i];
			i++;
			j++;
		}
		else if(a1[i] < a2[j])
		{
			i++;
		}
		else
		{
			j++;		
		}
	}
	
	return n;
}


void init_list(int* arr, int len)
{
	int n = 0;
	for(int i = 0; i < len; i++)
	{
		n += rand() % 5 + 1;
		arr[i] = n;
	}
}

void show_list(int* arr, int len)
{
	for(int i = 0; i < len; i++)
	{
		int cols = 10;
		if(i != 0 && i % cols == 0)
		{
			cout<<endl;
		}
		
		if(i % cols == 0)
		{
			cout<<setw(6)<<i / cols<<": ";
		}
		
		cout<<setw(8)<<arr[i];
	}
	cout<<endl;
}

inline int fw_search2(const int tag, int4 *arr, int len)
{
	if(tag == arr[0]) return 0;
	else if(tag < arr[0]) return -1;
	
	int m = 4;
	int pos = 2;
	
	while(pos < len)
	{
		if(tag == arr[pos])
			return pos;
		else if(tag < arr[pos])
			return binary_search(tag, arr, pos / 2, pos - 1);
		else
		{
			m <<= 1;
			pos = m - 2;
		}
	}
	
	return binary_search(tag, arr, pos / 2, len - 1);
}

inline int bw_search(const int tag, int* arr, int len)
{
	len--;
	if(tag == arr[len])
		return len;
	else if(tag > arr[len])
		return -len -1;
		
	int p = 2;
	
	
	while(p <= len)
	{
		if(tag == arr[len - p])
			return len - p;
		else if(tag > arr[len - p])
			return binary_search(tag, arr, len - p + 1, len - p / 2);
		else
			p = p * 2 + 2;
	}
	
	return binary_search(tag, arr, 0, len - p / 2);
}

int intersection(int* a1, int l1, int* a2, int l2)
{
	int n = 0;
	int n2 = 0;
	int *a = a1;
	int ll = l1;

	while(1)
	{
		if(!(l1 > 0 && l2 > 0)) break;
		
		int pos = fw_search2(a1[0], a2, l2);
		
		if(pos < 0)
		{
			pos = -pos - 1;
			a2 += pos;
			l2 -= pos;
		}
		else
		{
			a[n++] = a1[0];
			a2 += (pos + 1);
			l2 -= (pos + 1);
		}
		a1++;
		l1--;
		
		//cout<<"******"<<endl;
		//show_list(a1, l1);
		//show_list(a2, l2);
		
		
		if(!(l1 > 0 && l2 > 0)) break;
		
		
		pos = bw_search(a1[l1 - 1], a2, l2);
		//cout<<"---"<<pos<<endl;
		if(pos < 0)
		{
			l2 = -pos;
		}
		else
		{
			a[ll - ++n2] = a1[pos];
			//cout<<ll - n2<<","<<a1[pos]<<endl;
			l2 = pos;
		}
		l1--;
		
		//cout<<"******"<<endl;
		//show_list(a1, l1);
		//show_list(a2, l2);
		
		
		swap2(int*, a1, a2);
		swap(l1, l2);
		
	}
	//for(int i = 0; i < ll; i++)
	//{
	//	cout<<"* "<<a[i]<<endl;
	//}
	//cout<<"n1: "<<n<<", n2: "<<n2<<endl;
	for(int i = 0; i < n2; i++)
	{
		a[n + i] = a[ll - n2 + 1 + i];
	}
	return n + n2;
}

inline int binary_search(int4 tag, int4* arr, int l, int h)
{
	int m;
	while(l <= h)
	{
		m = (l + h) / 2;
		if(tag > arr[m])
			l = m + 1;
		else if(tag < arr[m])
			h = m - 1;
		else
			return m;
	}
	
	return -l - 1;
}
